package leetcode_jz_offer.day2_list;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * 输入：head = [1,3,2]
 * 输出：[2,3,1]
 **/

public class Num6_ReversePrintList {
//    ArrayList<Integer> arrayList=new ArrayList<>();
//    public int[] reversePrint(ListNode head) {
//        //2.递归-借用ArrayList顺序表,最后将arrayList转化为数组即可
//         //递归将结点逆序放在顺序表
//        reversePrintHelper(head);
//        //此时将顺序表的元素放在数组中即可
//        int size=arrayList.size();
//        int[] arr=new int[size];
//        for (int i = 0; i < size; i++) {
//            arr[i]=arrayList.get(i);
//        }
//        return arr;
//    }
//    //结点逆序放入顺序表
//    private void reversePrintHelper(ListNode head) {
//        if(head==null){
//            //节点遍历完毕,直接返回
//            return;
//        }
//        reversePrintHelper(head.next);
//        arrayList.add(head.val);
//    }
    public int[] reversePrint(ListNode head) {
        //方法1:通过栈来解决-先入栈的元素后弹出,将结点依次入栈,然后弹出结点时将对应结点的值给数组即可
        Stack<ListNode> stack=new Stack<>();
        ListNode node=head;
        while (node!=null){
            //将结点放入栈中
            stack.push(node);//把值直接入栈也可以,这样直接出战arr[i]=stack.pop()即可,这是注意栈中类型也得从Stack<ListNode>改为Stack<Integer>
            node=node.next;
        }
        //结点为空,开始出栈,值出到数组中
        int n=stack.size();//数组大小就是栈内元素大小
        int[] arr=new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=stack.pop().val;
        }
        return arr;
    }
}

 class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }
